Given an unsorted integer array nums, find the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Example 1:
Input: nums = [1,2,0] Output: 3
Example 2:
Input: nums = [3,4,-1,1] Output: 2
Example 3:
Input: nums = [7,8,9,11,12] Output: 1
Constraints:
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1
Average Rating: 3.65 (108 votes)
Solution
Approach 1: Index as a hash key.
Data clean up
First of all let's get rid of negative numbers and zeros since there is no
need of them. One could get rid of all numbers larger than n as well,
since the first missing positive is for sure smaller or equal to n + 1.
The case when the first missing positive is equal to n + 1 will be
treated separately.
What does it mean - to get rid of, if one has to keep O(N)
time complexity and hence could not pop unwanted elements out?
Let's just replace all these by 1s.
To ensure that the first missing positive is not 1, one has to verify
the presence of 1 before proceeding to this operation.
How to solve in-place
Now there we have an array which contains only positive numbers
in a range from 1 to n,
and the problem is to find a first missing positive in
O(N) time and constant space.
That would be simple, if one would be allowed to
have a hash-map positive number -> its presence for the array.
Sort of "dirty workaround" solution would be to allocate a string hash_str
with n zeros, and use it as a sort of hash map by changing
hash_str[i] to 1 each time one meets number i in the array.
Let's not use this solution, but just take away a pretty nice idea to use index as a hash-key for a positive number.
The final idea is to use index in nums as a hash key and sign of the element as a hash value which is presence detector.
For example, negative sign of
nums[2]element means that number2is present innums. The positive sign ofnums[3]element means that number3is not present (missing) innums.
To achieve that let's walk along the array (which after clean up contains
only positive numbers), check each element value elem
and change the sign of element nums[elem] to negative to mark
that number elem is present in nums. Be careful
with duplicates and ensure that the sign was changed only once.
Algorithm
Now everything is ready to write down the algorithm.
- Check if
1is present in the array. If not, you're done and1is the answer. - Replace negative numbers, zeros, and numbers larger than
nby1s. - Walk along the array. Change the sign of a-th element if you meet number
a. Be careful with duplicates : do sign change only once. Use index0to save an information about presence of numbernsince indexnis not available. - Walk again along the array. Return the index of the first positive element.
- If
nums[0] > 0returnn. - If on the previous step you didn't find the positive element in nums, that means
that the answer is
n + 1.
Implementation
Complexity Analysis
- Time complexity : O(N) since all we do here is four walks
along the array of length
N. - Space complexity : O(1) since this is a constant space solution.
April 27, 2020 5:08 AM
Another O(n) solution use cycle sort:
def firstMissingPositive(self, nums: List[int]) -> int:
i = 0
n = len(nums)
while i < n:
j = nums[i] - 1
# put num[i] to the correct place if nums[i] in the range [1, n]
if 0 <= j < n and nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
# so far, all the integers that could find their own correct place
# have been put to the correct place, next thing is to find out the
# place that occupied wrongly
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
May 5, 2020 7:50 PM
Solution with a string of length of n is not O(1) space complexity, it's O(n)
The problem should specify that it is ok if you alter the existing array because to my surprise the LeetCode solution doesn't care about modifying the existing array.
March 28, 2019 5:49 AM
Nice solution, but it's possible to do this in one pass, considering each value at most twice, and not destroying the contents of the array (though changing its order).
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
// We will partition the array into two sides, with one copy of each number
// on the left, in order, as far as possible.
// [1, 2, 3, 4, 5, ..., n][...(everything else, but not n+1)...].
int i = 0, end = nums.size();
// Call LeftPartition the interval [1, ..., i - 1]
// Call RightPartition the interval [nums[end], nums[nums.size() - 1]].
// Initially, both are empty.
// At the end, when "i" and "end" meet, call the results FinalLeftPartition and FinalRightPartition.
// Then the answer to the problem is 1 + size(FinalLeftPartition).
//
// We build those intervals in-place, by swapping elements when necessary, and updating i and end.
while (i != end) {
int val = nums[i];
if (val == 1 + i) // Number is in the right place. We may consider it part of LeftPartition, and advance i.
++i;
else if (
val > end // If this should go in FinalLeftPartition, then that would overlap with FinalRightPartition.
|| val <= 0 // The number is negative, it cannot possibly belong in FinalLeftPartition.
|| nums[val - 1] == val // This is a duplicate. It doesn't belong in FinalLeftPartition.
// How can we get away with checking just this one spot for a duplicate?
// See the next "else" branch -- we always put values into this exact spot.
) {
// If any of the above statements is true, this value doesn't need to be in FinalLeftPartition.
// So we may put it in the right partition,
// and advance "end".
swap(nums[i], nums[--end]);
// Now nums[i] has some new value that we haven't considered before, so
// leave "i" as is and go back to the top of the loop.
} else {
// We don't yet know whether val should be in
// FinalLeftPartition or FinalRightPartition, so put it in neither.
// In order to consider another value, place val so that it matches its own index;
// that is, place it where it will be if indeed it ends up in FinalLeftPartition,
// and next consider the element there.
swap(nums[i], nums[val - 1]);
// We learned nothing new about what elements will be in FinalLeftPartition or FinalRightPartition,
// and nums[i] has the previous value of nums[val - i], which we haven't dealt with yet,
// so continue the loop without advancing either pointer.
// But we did make useful progress in this branch: now in the future, if we see the same "val"
// again, we will know it's a duplicate, because of the "nums[val - 1] == val" check above!
}
}
return i + 1;
}
};
Last Edit: June 25, 2019 8:30 AM
One could get rid of all numbers larger than n as well, since the first missing positive is for sure smaller or equal to n + 1
This isn't obvious and could use some more explanation.
I find solutions that just state something without proving it to be especially annoying.
I tried to give an explanation here:
This doesn't really count as O(1) because it relies on destructively modifying the input, and in almost any real life use case, you never want your functions to modify the input data.
May 7, 2020 11:43 AM
we can apply cyclic replacement which cost O(n) to swap and put all numbers in their correct positions in array
class Solution {
public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i ++){
int curr = nums[i];
// curr-1 is the next index to swap and must be inside bound
while (curr-1 >= 0 && curr-1 < nums.length && nums[curr - 1] != curr){
int temp = nums[curr - 1];
nums[curr - 1] = curr;
curr = temp;
}
}
for (int i = 0; i < nums.length; i ++){
if (nums[i] != i + 1) return i + 1;
}
return nums.length + 1;
}
}
Should the following statement:
If array contains only one element and it's not 1, the answer is 2.
be:
If array contains only one element and it's 1, the answer is 2.
?
just use a heap..
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
heapq.heapify(nums)
num = 1
for i in range(len(nums)):
x = heapq.heappop(nums)
if (x > 0 and x==num):
num+=1
return num
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/15/2021 08:12 | Accepted | 100 ms | 66.1 MB | cpp |
| 07/28/2020 19:13 | Accepted | 4 ms | 9.8 MB | cpp |
| 07/28/2020 19:11 | Wrong Answer | N/A | N/A | cpp |
| 07/28/2020 19:11 | Wrong Answer | N/A | N/A | cpp |
| 05/02/2020 20:01 | Accepted | 0 ms | 10.1 MB | cpp |
xxxxxxxxxxclass Solution {public: int firstMissingPositive(vector<int>& nums) { // check if 1 is present in array bool isOne = false; int n = nums.size(); for(int i=0;i<n;i++) { if(nums[i] == 1) isOne = true; } if(isOne == false) return 1; // replace numbers out of range 1 - n by 1s for(int i=0;i<n;i++) { if(nums[i]<1 || nums[i]>n) nums[i] = 1; } // change sign of ath element if a is present in array for(int i=0;i<n;i++) { int a = abs(nums[i]); if(a == n) nums[0] = -abs(nums[0]); else nums[a] = -abs(nums[a]); } // take index of first positive integer (the missing number) for(int i=1;i<n;i++) { if(nums[i] > 0) return i; } // check whether it was the nth element if(nums[0] > 0) return n; // if no element found positive, answer would be the next positive number since 1-n are already present return n+1; }};



